// https://leetcode.cn/problems/arranging-coins/
// Created by ade on 2022/8/5.
//
#include <iostream>
#include <math.h>

using namespace std;

class Solution {
public:
    int arrangeCoins(int n) {
        if(n == 1) return 1;
        int left = 0, right = n;
        while (left < right) {
            int mid = (left + right) / 2;
            long long res = (long long)mid * (mid + 1) / 2;
            if (res == n) return mid;
            if (res > n) right = mid;
            else left = mid + 1;
        }
        return left - 1;
    }
};

int main() {
    Solution so;
    cout << so.arrangeCoins(5) << endl;
    return 0;
}